package com.test.daily.leetcode.y2022.m07.day0713.v01;

/**
 * @descriptions:
 * @author: Tom
 * @date: 2022/7/13 下午 11:15
 * @version: 1.0
 */
public class Solution {
    public static class MyHeap{
        int[] heap;
        int limit;
        int heapSize;
        public MyHeap(int limit){
            this.limit = limit;
            heapSize = 0;
            heap = new int[limit];
        }
        public boolean isEmpty(){
            return this.heapSize == 0;
        }
        public boolean isFull(){
            return this.heapSize == this.limit;
        }
        public void swap(int[] arr, int i, int j){
            int tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
        }
        public void push(int value){
            if(this.heapSize == limit){
                throw new RuntimeException("is full");
            }
            heap[heapSize] = value;
            heapInsert(heap, heapSize++);
        }
        public int pop(){
            int ans = heap[0];
            swap(heap, 0, heapSize--);
            heapify(heap, 0);
            return ans;
        }
        public void heapInsert(int[] arr, int index){
            while(arr[index] < arr[(index-1)/2]){
                swap(arr, index, (index-1)/2);
                index = (index-1)/2;
            }
        }
        public void heapify(int[] arr, int index){
            int left = index * 2 + 1;
            while(left < heapSize){
                int largest = left + 1 < limit && arr[left+1] > arr[left] ? left+1: left;
                largest = arr[index] > arr[largest] ? index: largest;
                if(index == largest){
                    break;
                }
                swap(arr, index, largest);
                index = largest;
                left = index * 2 + 1;
            }
        }
    }
}
